#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>


#define numberOfNodesRandom		10
#define numberOfNodes2D			13000
#define numberOfNodes3D			10
#define numberOfNodes4D			10

////This struct defines a graph with random edges 0-1. It is represented as a 2 dimensional array, where the weight of the edge between i and j is graph[i][j] or graph[j][i]
//typedef struct randomEdgeGraph {
//	double edges[numberOfNodesRandom][numberOfNodesRandom];
//}REG;

//this struct defines an edge. Any graph is converted into an array of these structs, which is then sorted and passed to the DoKruskals to find the MST.
typedef struct graphEdge_struct {
	double edgeWeight;
	int node1;
	int node2;
}graphEdge;

//this struct defines a node for a graph whose nodes all reside in the x-y plane and on the unit square
typedef struct graphNode2D_struct {
	double x;
	double y;
	int idenifier;
}node2D;

//this struct defines a node for a graph whose nodes all reside in the x-y-z space and in or on the unit cube
typedef struct graphNode3D_struct {
	double x;
	double y;
	double z;
	int identifier;
}node3D;

//this struct defines a node for a graph whose nodes all reside in the 4 dimensional space inside the unit hypercube
typedef struct graphNode4D_struct {
	double x;
	double y;
	double z;
	double r;
	int identifier;
}node4D;

////This function constructs a randomEdgeGraph. It uses the current system time to seed the random number generator and does make sure that graph[i][j] == graph[j][i]
//REG getNewRandom(){
//	int i;
//	int k;
//	int j;
//	double r;
//	REG newGraph;
//	unsigned int iseed = (unsigned int)time(NULL);
//	srand(iseed);
//
//	for(i=0;i<numberOfNodesRandom;i++){
//		for(k=0;k<numberOfNodesRandom;k++){
//			newGraph.edges[i][k] = 0.0;
//		}
//	}
//
//	for(i=0;i<numberOfNodesRandom;i++){
//		for(k=0;k<numberOfNodesRandom;k++){
//			if(newGraph.edges[k][i] == 0.0){
//				
//				r = rand() /(RAND_MAX+1.0);
//				newGraph.edges[k][i] = r;
//				newGraph.edges[i][k] = r;
//			}
//		}
//	}
//
//	return newGraph;
//}

//This function iterates through a randomEdgeGraph and loads all of the edges into the array edgeArr. It does make sure to only include each edge once, 
//since in our multidimensional array we have 2 ways to refer to any edge. (graph[i][j] == graph[j][i]) 
//void getAllEdges(REG graph,graphEdge* edgeArr){
//	int i;
//	int k;
//	int j;
//	graphEdge tempEdge;
//	j=0;
//
//	for(i=0;i<numberOfNodesRandom;i++){
//		for(k=i;k<numberOfNodesRandom;k++){
//			if(i!=k){
//				tempEdge.node1 = i;
//				tempEdge.node2 = k;
//				tempEdge.edgeWeight = graph.edges[i][k];
//				edgeArr[j] = tempEdge;
//				j++;
//			}
//		}
//	}
//}
//
////This function prints the start and end nodes for each edge along with the edges weight for a randomEdgeGraph
//void printGraph(REG graph){
//	int i;
//	int k;
//	char mainArr2[50];
//	char temp1[20];
//	char temp2[20];
//	char temp3[20];
//
//	for(i=0;i<numberOfNodesRandom;i++){
//		for(k=i;k<numberOfNodesRandom;k++){
//			if(i!=k){
//				sprintf(temp3,"%lf",graph.edges[i][k]);
//				itoa(i,temp1,10);
//				itoa(k,temp2,10);
//				strcpy(mainArr2, "Edge: ");
//				strcat(mainArr2, temp1);
//				strcat(mainArr2, "-");
//				strcat(mainArr2, temp2);
//				strcat(mainArr2, " Weight: ");
//				strcat(mainArr2, temp3);
//				strcat(mainArr2, "\n");
//				printf(mainArr2);
//			}
//		}
//	}
//}

//this function returns the maximum number of edges in a complete graph of order n (where n is the number of nodes)
int getMaxEdges(int nodes){
	return (int)(nodes*(((double)nodes)-1)/2.0);
}

//this is a helper function used to sort an array of edges from decreasing to increasing.
int sort(const void *x, const void *y) {
	if((*(graphEdge*)x).edgeWeight > (*(graphEdge*)y).edgeWeight){
		return 1;
	} else if((*(graphEdge*)x).edgeWeight < (*(graphEdge*)y).edgeWeight){
		return -1;
	} else {
		return 0;
	}
}

//This function actually runs Kruskals algorithm. Loads the MST into the mstArr that is passed into the function. note: this is probably not done in the most efficient manner, consider refractoring
void DoKruskals(graphEdge* edges, int maxEdges, graphEdge* mstArr){
	int sets[numberOfNodesRandom][numberOfNodesRandom];
	int setPos[numberOfNodesRandom];
	int i;
	int k;
	int pos1;
	int pos2;
	int j;

	j = 0;

	for(i=0;i<numberOfNodesRandom;i++){
		sets[i][0] = i;
		setPos[i] = 1;
		for(k=1;k<numberOfNodesRandom;k++)
		{
			sets[i][k]=-1;
		}
	}

	for(i=0;i<maxEdges;i++){
		pos1 = findInSet(sets,edges[i].node1);
		pos2 = findInSet(sets,edges[i].node2);
		if(pos1 != pos2){
			mstArr[j] = edges[i];
			j++;
			for(k=0;k<numberOfNodesRandom;k++){
				if(sets[pos2][k] != -1){
					sets[pos1][setPos[pos1]] = sets[pos2][k];
					sets[pos2][k] = -1;
					setPos[pos1]++;
				} else {
					break;
				}
			}
		}
	}

}

//this function finds which set a given node is located in. Used as part of the "data structure" that is needed to perform Kruskals algorithm.
int findInSet(int setsArr[numberOfNodesRandom][numberOfNodesRandom], int node){
	int i;
	int k;
	int returnPos;
	
	returnPos = -1;
	for(i=0;i<numberOfNodesRandom;i++){
		for(k=0;k<numberOfNodesRandom;k++){
			if(setsArr[i][k] == node){
				returnPos = i;
				break;
			} else if(setsArr[i][k] == -1){
				break;
			}
		}
		if(returnPos!=-1){
			break;
		}
	}
	return returnPos;
}

//this builds a new graph whose nodes are located on the x-y plane in the unit square
void doBuild2DGraph(node2D graph[numberOfNodes2D]){
	int i;
	node2D tempNode;
	unsigned int iseed = (unsigned int)time(NULL);
	srand(iseed);

	for(i=0;i<numberOfNodes2D;i++){
		tempNode.x = rand() /(RAND_MAX+1.0);
		tempNode.y = rand() /(RAND_MAX+1.0);
		tempNode.idenifier = i;
		graph[i] = tempNode;
	}
}

//this function returns the distance between 2 2d vectors.
double getDistance2d(double x1, double y1, double x2, double y2){
	return (double)(sqrt(pow((x2-x1),2)+pow((y2-y1),2)));
}

//this function returns the distance between 2 3d vectors
double getDistance3d(double x1, double y1, double z1, double x2, double y2, double z2)
{
	return (double)(sqrt(pow((x2-x1),2)+pow((y2-y1),2)+pow((z2-z1),2)));
}

//this function returns the distance between 2 4d vectors
double getDistance4d(double x1, double y1, double z1, double r1, double x2, double y2, double z2, double r2)
{
	return (double)(sqrt(pow((x2-x1),2)+pow((y2-y1),2)+pow((z2-z1),2)+pow((r2-r1),2)));
}

//this gets all edges out of a 2d graph
void GetAllEdges2d(graphEdge * edgeArr, node2D nodes[numberOfNodes2D]){
	int i;
	int k;
	int j;
	graphEdge tempEdge;

	j=0;

	for(i=0;i<numberOfNodesRandom;i++){
		for(k=i;k<numberOfNodesRandom;k++){
			if(i!=k){
				tempEdge.node1 = i;
				tempEdge.node2 = k;
				tempEdge.edgeWeight = getDistance2d(nodes[i].x,nodes[i].y,nodes[k].x,nodes[k].y);;
				edgeArr[j] = tempEdge;
				j++;
			}
		}
	}
}

//this function builds a graph whose nodes are all located in the x-y-z space and lie in or on the unit cube
void Build3dGraph(node3D graph[numberOfNodes3D]){
	int i;
	node3D tempNode;
	unsigned int iseed = (unsigned int)time(NULL);
	srand(iseed);

	for(i=0;i<numberOfNodes3D;i++){
		tempNode.x = rand() /(RAND_MAX+1.0);
		tempNode.y = rand() /(RAND_MAX+1.0);
		tempNode.z = rand() /(RAND_MAX+1.0);
		tempNode.identifier = i;
		graph[i] = tempNode;
	}
}

//this extracts all of the edges out of a 3d graph
void getAllEdges3d(graphEdge * edgeArr, node3D nodes[numberOfNodes3D]){
	int i;
	int k;
	int j;
	graphEdge tempEdge;

	j=0;

	for(i=0;i<numberOfNodesRandom;i++){
		for(k=i;k<numberOfNodesRandom;k++){
			if(i!=k){
				tempEdge.node1 = i;
				tempEdge.node2 = k;
				tempEdge.edgeWeight = getDistance3d(nodes[i].x,nodes[i].y,nodes[i].z,nodes[k].x,nodes[k].y,nodes[i].z);;
				edgeArr[j] = tempEdge;
				j++;
			}
		}
	}
}

//this builds a graph whose nodes are all located in the 4 dimensional space of the unit hypercube
void Build4DGraph(node4D graph[numberOfNodes4D]){
	int i;
	node4D tempNode;
	unsigned int iseed = (unsigned int)time(NULL);
	srand(iseed);

	for(i=0;i<numberOfNodes4D;i++){
		tempNode.x = rand() /(RAND_MAX+1.0);
		tempNode.y = rand() /(RAND_MAX+1.0);
		tempNode.z = rand() /(RAND_MAX+1.0);
		tempNode.r = rand() /(RAND_MAX+1.0);
		tempNode.identifier = i;
		graph[i] = tempNode;
	}
}

//this function extracts all of the edges from a 4d graph
void getAllEdges4d(graphEdge * edgeArr, node4D nodes[numberOfNodes4D]){
	int i;
	int k;
	int j;
	graphEdge tempEdge;

	j=0;

	for(i=0;i<numberOfNodesRandom;i++){
		for(k=i;k<numberOfNodesRandom;k++){
			if(i!=k){
				tempEdge.node1 = i;
				tempEdge.node2 = k;
				tempEdge.edgeWeight = getDistance4d(nodes[i].x,nodes[i].y,nodes[i].z,nodes[i].r,nodes[k].x,nodes[k].y,nodes[k].z,nodes[k].r);
				edgeArr[j] = tempEdge;
				j++;
			}
		}
	}
}

void getAllRandomEdgesNew(graphEdge * edgeArr){
	int i;
	int k;
	int j;
	graphEdge tempEdge;
	unsigned int iseed = (unsigned int)time(NULL);
	srand(iseed);

	j=0;

	for(i=0;i<numberOfNodesRandom;i++){
		for(k=i;k<numberOfNodesRandom;k++){
			if(i!=k){
				tempEdge.node1 = i;
				tempEdge.node2 = k;
				tempEdge.edgeWeight = rand() /(RAND_MAX+1.0);
				edgeArr[j] = tempEdge;
				j++;
			}
		}
	}
}

main()
{
	int i;
	int maxRandomEdges;
	int max2dEdges;
	int max3dEdges;
	int max4dEdges;
	char intStr[10];
	char doubleStr[20];
	//REG newGraph;
	graphEdge * edges;
	graphEdge * randomMst;

	node2D nodes2d[numberOfNodes2D];
	graphEdge * edges2d;
	graphEdge * edges2dMST;

	node3D nodes3d[numberOfNodes3D];
	graphEdge * edges3d;
	graphEdge * edges3dMST;

	node4D nodes4d[numberOfNodes4D];
	graphEdge * edges4d;
	graphEdge * edges4dMST;


	maxRandomEdges = getMaxEdges(numberOfNodesRandom);
	max2dEdges = getMaxEdges(numberOfNodes2D);
	max3dEdges = getMaxEdges(numberOfNodes3D);
	max4dEdges = getMaxEdges(numberOfNodes4D);

	edges = (graphEdge*) calloc(maxRandomEdges,sizeof(graphEdge));
	randomMst = (graphEdge*) calloc(numberOfNodesRandom-1,sizeof(graphEdge));

	edges2d = (graphEdge*) calloc(max2dEdges,sizeof(graphEdge));
	edges2dMST = (graphEdge*) calloc(numberOfNodes2D-1,sizeof(graphEdge));

	edges3d = (graphEdge*) calloc(max2dEdges,sizeof(graphEdge));
	edges3dMST = (graphEdge*) calloc(numberOfNodes3D-1,sizeof(graphEdge));

	edges4d = (graphEdge*) calloc(max2dEdges,sizeof(graphEdge));
	edges4dMST = (graphEdge*) calloc(numberOfNodes4D-1,sizeof(graphEdge));

	/*newGraph = getNewRandom();

	getAllRandomEdgesNew(edges);
	qsort(edges,maxRandomEdges,sizeof(graphEdge),sort);

	
	DoKruskals(edges, maxRandomEdges, randomMst);

	for(i=0;i<maxRandomEdges;i++){
		if(randomMst[i].edgeWeight != 0.0){
			sprintf(doubleStr,"%lf",randomMst[i].edgeWeight);
			itoa(randomMst[i].node1,intStr,10);
			strcat(doubleStr," :");
			strcat(doubleStr,intStr);
			strcat(doubleStr,"-");
			itoa(randomMst[i].node2,intStr,10);
			strcat(doubleStr,intStr);
			strcat(doubleStr,"\n");
			printf(doubleStr);
		}
	}*/
	printf("%d",max2dEdges);
	doBuild2DGraph(nodes2d);
	GetAllEdges2d(edges2d,nodes2d);
	qsort(edges2d,max2dEdges,sizeof(graphEdge),sort);
	DoKruskals(edges2d, max2dEdges, edges2dMST);
	printf("done");
	/*printf("Now for the 2d:\n");
	for(i=0;i<max2dEdges;i++){
		if(edges2dMST[i].edgeWeight != 0.0){
			sprintf(doubleStr,"%lf",edges2dMST[i].edgeWeight);
			itoa(edges2dMST[i].node1,intStr,10);
			strcat(doubleStr," :");
			strcat(doubleStr,intStr);
			strcat(doubleStr,"-");
			itoa(edges2dMST[i].node2,intStr,10);
			strcat(doubleStr,intStr);
			strcat(doubleStr,"\n");
			printf(doubleStr);
		}
	}


	printf("Now for the 3d:\n");
	Build3dGraph(nodes3d);
	getAllEdges3d(edges3d,nodes3d);
	qsort(edges3d,max3dEdges,sizeof(graphEdge),sort);
	DoKruskals(edges3d, max3dEdges, edges3dMST);
	for(i=0;i<max3dEdges;i++){
		if(edges3dMST[i].edgeWeight != 0.0){
			sprintf(doubleStr,"%lf",edges3dMST[i].edgeWeight);
			itoa(edges3dMST[i].node1,intStr,10);
			strcat(doubleStr," :");
			strcat(doubleStr,intStr);
			strcat(doubleStr,"-");
			itoa(edges3dMST[i].node2,intStr,10);
			strcat(doubleStr,intStr);
			strcat(doubleStr,"\n");
			printf(doubleStr);
		}
	}

	printf("Now for the 4d:\n");
	Build4DGraph(nodes4d);
	getAllEdges4d(edges4d,nodes4d);
	qsort(edges4d,max4dEdges,sizeof(graphEdge),sort);
	DoKruskals(edges4d, max4dEdges, edges4dMST);
	for(i=0;i<max4dEdges;i++){
		if(edges4dMST[i].edgeWeight != 0.0){
			sprintf(doubleStr,"%lf",edges4dMST[i].edgeWeight);
			itoa(edges4dMST[i].node1,intStr,10);
			strcat(doubleStr," :");
			strcat(doubleStr,intStr);
			strcat(doubleStr,"-");
			itoa(edges4dMST[i].node2,intStr,10);
			strcat(doubleStr,intStr);
			strcat(doubleStr,"\n");
			printf(doubleStr);
		}
	}*/

	//sprintf(intStr,"%lf",newGraph.edges[0][8]);
	//strcat(intStr,"\n");
	//printf(intStr);
	
	//printGraph(newGraph);
	//printf("%d",getMaxEdges());
	getchar();
}



